package com.circuit.euler;

import java.util.ArrayList;
import java.util.Iterator;

public class Fleury {

        /* 
         * fonction pont qui prend en paramétre l'arete en question et renvoi vrai si l'aréte est un isthme et faux sinn.
         */
        public static boolean isthme (Arete a, Graphe g){
                Graphe f = g;
                int i = a.getS1();
                int j = a.getS2();

                return !existeChemin(f, i, j, new ArrayList<Integer>(), i);
        }

        /**
         * fonction qui teste si il existe un chemin autre que l'arete elle meme du somme gauche jusqu'au sommet droite
         */
        static boolean existeChemin(Graphe graphe, int i, int j, ArrayList<Integer> chemins, int d) {
                int tmp = -1;
                chemins.add(d);
                // ici si on rentre dans le if cela signifie qu'on se situe au de but de la recherche du chemin donc il faut trouver un autre chemin que ne passe pas par j mais qui se termine par j. 
                if(chemins.size()==1){
                        tmp = chercherSommetSansB(graphe.getSommetsIncidents(d),chemins,j); //on cherche un sommet voisin en evitant le sommet j
                        if(tmp == -1) return false; //Si aucun sommet n'est trouvé, le chemin n'existe pas
                        else return existeChemin(graphe,i,j,chemins,tmp);//sinon on continue notre chemin a partir du sommet trouvé
                }
                else{//Cas ou chemins contient plus d'un élement
                        tmp = chercherSommetAvecB(graphe.getSommetsIncidents(d),chemins,j);//on cherche un sommet voisin de d avec en priorite le sommet j
                        if(tmp == -1) return false;//Si aucun sommet n'est trouver, le chemin n'existe pas
                        else if(tmp == j) return true;//Si le sommet trouver est j il existe un chemin entre i et j et on retourne true
                        else return existeChemin(graphe,i,j,chemins,tmp); //sinon on continue la recherche
                }
        }

        /*
         * Cherche un sommet de la liste rch qui ne se trouve pas dans dejaP et qui n'est pas le sommet b
         * Renvoie -1 si aucun sommet n'est trouve
         */
        static Integer chercherSommetSansB(ArrayList<Integer> rch,ArrayList<Integer> dejaP,Integer b){
                boolean parcouru = true;

                Iterator<Integer> it = rch.iterator();
                while (it.hasNext()){//Parcours de la liste rch
                        Integer i = it.next();
                        Iterator<Integer> it2 = dejaP.iterator();
                        parcouru = true;
                        while(it2.hasNext()){//Parcours de la liste dejaP
                                Integer j = it2.next();
                                if(i == j)//Si le sommet se trouve dans la liste on va changer de sommet
                                        parcouru = false;
                        }
                        if(i != b && parcouru == true)//Si le sommet est pas dans la liste dejaP et n'est pas b on le renvoie
                                return i;
                        //Sinon on continue de chercher dans rch
                }
                //Si aucun sommet n'est trouver, on retourne -1
                return -1;
        }

        /*
         * Cherche un sommet de la liste rch qui ne se trouve pas dans dejaP et qui est de preference le sommet b
         * Renvoie -1 si aucun sommet n'est trouve
         */
        static Integer chercherSommetAvecB(ArrayList<Integer> rch,ArrayList<Integer> dejaP,Integer b){
                boolean parcouru = true;
                Integer tmp = -1;
                Iterator<Integer> it = rch.iterator();
                while (it.hasNext()){//Parcours de la liste rch
                        Integer i = it.next();
                        if( i == b)//Si le sommet trouve est le sommet rechercher on renvoie i
                                return i;
                        Iterator<Integer> it2 = dejaP.iterator();
                        parcouru = true;
                        while(it2.hasNext()){//Parcours de la liste dejaP
                                Integer j = it2.next();
                                if(i == j)//Si le sommet se trouve dans la liste on va changer de sommet
                                        parcouru = false;
                        }
                        if(parcouru == true)//Si le sommet n'est pas dans la liste dejaP on renvoie ce sommet
                                tmp=i;
                        //Sinon on continue de chercher dans rch
                }
                // On retourne le sommet trouve ou -1 sinon
                return tmp;
        }


        /*
         * Algorithme de Fleury qui renvoie le cycle eulerien du graphe g a partir du sommet sommet
         */
        public static String algoFleury(Graphe g, int sommet){

                String cycle = Integer.toString(sommet) + ' ';
                int x = sommet;
                Graphe f = g;

                if(g.getSommetsIncidents(sommet).size() == 0)
                        return "Aucun cycle eulerien pour ce graphe !";

                else{

                        while(!f.getSommetsIncidents(x).isEmpty()){
                                Arete e = new Arete(x, f.getSommetsIncidents(x).get(0));
                                if(isthme(e, f)){
                                        for(Integer v : f.getSommetsIncidents(x)){
                                                e = new Arete (x,v);
                                                if(!isthme(e, f)){
                                                        break;
                                                }
                                                else{
                                                }
                                        }
                                }
                                x = e.getS2();
                                cycle += Integer.toString(x) + " \n";
                                f.enleverArete(e);
                        }
                        if(x == sommet){
                                return cycle;
                        }
                        else
                                return "Aucun cycle eulerien pour ce graphe !";
                }
        }
}

